๐Ÿ‘ฉโ€๐Ÿ’ป 81303. ํ‘œ ํŽธ์ง‘

@Seongukbaek Posted May 04, 2022 ยท Updated May 04, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ํ‘œ ํŽธ์ง‘

๐Ÿ“ Logic

private void init() { for (int i = 0; i < n; i++) { pre[i] = i - 1; next[i] = i + 1; } next[n - 1] = -1; }
  • ํ˜„์žฌ node์˜ ์ด์ „๊ณผ ์ดํ›„ node๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฐ์—ด์„ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
public void delete() { trash.push(new Node(now, pre[now], next[now])); // now์˜ pre์™€ next๋ฅผ updateํ•จ์œผ๋กœ์จ ํ•ด๋‹น node๋ฅผ ์ œ๊ฑฐ if (pre[now] != -1) next[pre[now]] = next[now]; if (next[now] != -1) pre[next[now]] = pre[now]; // ํ•ด๋‹น ์œ„์น˜๋Š” ์›๋ณธ๊ณผ ๋‹ฌ๋ผ์ง€๋ฏ€๋กœ X๋กœ ๋ณ€๊ฒฝ sb.setCharAt(now, 'X'); // now ์ด๋™ if(next[now] != -1) now = next[now]; else now = pre[now]; } public void undo() { Node insert = trash.pop(); // ๋‹ค์‹œ ์ถ”๊ฐ€ํ•  insert node์˜ pre์™€ next๋ฅผ updateํ•จ์œผ๋กœ์จ ํ•ด๋‹น node๋ฅผ ์ถ”๊ฐ€ if (insert.before != -1) next[insert.before] = insert.cur; if (insert.after != -1) pre[insert.after] = insert.cur; // ์›์ƒ๋ณต๊ตฌ sb.setCharAt(insert.cur, 'O'); }
  • goUp() ๊ณผ goDown() ์œผ๋กœ now ๋ฅผ ๊ณ„์† ์ตœ์‹ ํ™”ํ•˜๊ณ , ์‚ญ์ œ ๋ฐ ๋ณต๊ตฌ ์‹œ์—๋Š” pre ์™€ next ๋ฐฐ์—ด์„ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Node { int cur; int before; int after; public Node(int cur, int before, int after) { this.cur = cur; this.before = before; this.after = after; } } class Table { StringBuilder sb; Stack<Node> trash = new Stack<>(); // ํ˜„์žฌ node์˜ ์ด์ „๊ณผ ์ดํ›„ node๋ฅผ ์ €์žฅํ•  ๋ฐฐ์—ด int[] pre; int[] next; int n; int now; public Table(int n, int now) { this.n = n; this.now = now; pre = new int[n]; next = new int[n]; sb = new StringBuilder("O".repeat(n)); init(); } private void init() { for (int i = 0; i < n; i++) { pre[i] = i - 1; next[i] = i + 1; } next[n - 1] = -1; } // ์ค‘๊ฐ„์— ์‚ญ์ œ๋œ node๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ๊ธฐ์— n๋งŒํผ ๋ฐ˜๋ณตํ•˜๋ฉด์„œ now ์ด๋™ public void goUp(int n) { while(n-- > 0) now = pre[now]; } public void goDown(int n) { while(n-- > 0) now = next[now]; } public void delete() { trash.push(new Node(now, pre[now], next[now])); // now์˜ pre์™€ next๋ฅผ updateํ•จ์œผ๋กœ์จ ํ•ด๋‹น node๋ฅผ ์ œ๊ฑฐ if (pre[now] != -1) next[pre[now]] = next[now]; if (next[now] != -1) pre[next[now]] = pre[now]; // ํ•ด๋‹น ์œ„์น˜๋Š” ์›๋ณธ๊ณผ ๋‹ฌ๋ผ์ง€๋ฏ€๋กœ X๋กœ ๋ณ€๊ฒฝ sb.setCharAt(now, 'X'); // now ์ด๋™ if(next[now] != -1) now = next[now]; else now = pre[now]; } public void undo() { Node insert = trash.pop(); // ๋‹ค์‹œ ์ถ”๊ฐ€ํ•  insert node์˜ pre์™€ next๋ฅผ updateํ•จ์œผ๋กœ์จ ํ•ด๋‹น node๋ฅผ ์ถ”๊ฐ€ if (insert.before != -1) next[insert.before] = insert.cur; if (insert.after != -1) pre[insert.after] = insert.cur; // ์›์ƒ๋ณต๊ตฌ sb.setCharAt(insert.cur, 'O'); } public String print() { return sb.toString(); } } class Solution { public String solution(int n, int k, String[] cmd) { Table t = new Table(n, k); for (String c : cmd) { switch (c.charAt(0)) { case 'U' -> t.goUp(Integer.parseInt(c.substring(2))); case 'D' -> t.goDown(Integer.parseInt(c.substring(2))); case 'C' -> t.delete(); case 'Z' -> t.undo(); } } // ์ตœ์ข…์ ์œผ๋กœ ํ‘œ๋ฅผ ๋น„๊ตํ•˜์—ฌ answer๋ฅผ ์™„์„ฑํ•˜๋Š” method return t.print(); } }

โœ๏ธ Review

  • ์ฒ˜์Œ ๊ตฌํ˜„์€ List ์™€ Stack ์„ ์ด์šฉํ–ˆ๋‹ค. ์‹คํŒจํ•œ ํ…Œ์ผ€๊ฐ€ ๋„ˆ๋ฌด ๋งŽ์•˜๊ณ , ํšจ์œจ์„ฑ์€ ์•„์˜ˆ ๋Œ์•„๊ฐ€์ง€๋„ ์•Š์•˜๋‹ค.
  • ์š”์†Œ์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ์ž์ฃผ ์ผ์–ด๋‚˜๊ธฐ์—, ์ด์— ์ ํ•ฉํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ํ•„์š”ํ•œ ๊ฒƒ ๊ฐ™์•˜๋‹ค. ์ด์—๋Š” LinkedList ๊ฐ€ ์ ํ•ฉํ•ด๋ณด์˜€๋‹ค.
  • ์ƒ๊ฐ๋ณด๋‹ค ์‰ฌ์›Œ๋ณด์˜€์œผ๋‚˜, ๊ตฌํ˜„ํ• ์ˆ˜๋ก ๊ผผ๊ผผํžˆ ์ƒ๊ฐํ•ด์•ผ ํ•  ๊ตฌํ˜„๋ถ€๋“ค์ด ์ƒ๊ฒจ๋‚˜, ์ฐธ๊ณ ๊ฐ€ ํ•„์š”ํ–ˆ๋‹ค...
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€